/*
 * @lc app=leetcode.cn id=46 lang=javascript
 *
 * [46] 全排列
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  //  该方案使用递归回溯的方式，
  // 1. 递归参数为: unusedNums（当前未被使用到的数，已加入到排列的数将会赋值为null）以及 usedNums（已加入到排列的数）
  // 2. 单层搜索的逻辑: 我们在递归函数中遍历unusedNums;当其元素不等于null时，证明该数未加入到排列，此时我们将其加入到排列并标识其为已被使用(unusedNums[i]=null)，然后将二者作为新的参数继续递归
  // 3. 递归截止条件: 直到已加入到排列的数的数量等于给定数组元素的数量则证明所有数排列完成，此时添加结果，停止递归。

  const res = [];
  backtracking(nums, []);
  return res;

  function backtracking(unusedNums, usedNums) {
    if (usedNums.length === nums.length) {
      res.push(usedNums);
      return;
    }
    for (let i = 0; i < unusedNums.length; i++) {
      if (unusedNums[i] !== null) {
        const tmp = [...unusedNums];
        const tmpUsedNums = [...usedNums, tmp[i]];
        tmp[i] = null;
        backtracking(tmp, tmpUsedNums);
      }
    }
  }
};
// @lc code=end
